/*
 * @lc app=leetcode.cn id=10 lang=c
 *
 * [10] 正则表达式匹配
 *
 * https://leetcode-cn.com/problems/regular-expression-matching/description/
 *
 * algorithms
 * Hard (30.81%)
 * Likes:    1915
 * Dislikes: 0
 * Total Accepted:    148K
 * Total Submissions: 479.1K
 * Testcase Example:  '"aa"\n"a"'
 *
 * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 * 
 * 
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 
 * 
 * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：s = "aa" p = "a"
 * 输出：false
 * 解释："a" 无法匹配 "aa" 整个字符串。
 * 
 * 
 * 示例 2:
 * 
 * 
 * 输入：s = "aa" p = "a*"
 * 输出：true
 * 解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
 * 
 * 
 * 示例 3：
 * 
 * 
 * 输入：s = "ab" p = ".*"
 * 输出：true
 * 解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
 * 
 * 
 * 示例 4：
 * 
 * 
 * 输入：s = "aab" p = "c*a*b"
 * 输出：true
 * 解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
 * 
 * 
 * 示例 5：
 * 
 * 
 * 输入：s = "mississippi" p = "mis*is*p*."
 * 输出：false
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 0 
 * 0 
 * s 可能为空，且只包含从 a-z 的小写字母。
 * p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
 * 保证每次出现字符 * 时，前面都匹配到有效的字符
 * 
 * 
 */

// @lc code=start
#include <stdbool.h>
#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>

bool isMatchCore(char *s, char *p)
{
    if (*s == '\0' && *p == '\0')
        return true;
    else if (*s != '\0' && *p == '\0')
        return false;
    else if (*(p + 1) == '*')
    {
        if (*s == *p || (*p == '.' && *s != '\0'))
        {
            return 
                isMatchCore(s, p + 2) || 
                isMatchCore(s + 1, p) || 
                isMatchCore(s + 1, p + 2);
        }
        else 
            return isMatchCore(s, p + 2);
    }
    else if (*s == *p || (*p == '.' && *s != '\0'))
        return isMatchCore(s + 1, p + 1);
    else
        return false;
}

bool isMatch(char *s, char *p)
{
    if (s == NULL || p == NULL)
        return false;
    else
        return isMatchCore(s, p);
}

int main(int argc, char *argv[])
{   
    char *s = "aaaaaaaaaaaaaaaaaaab", *p = "a*a*a*a*a*a*a*a*a*a*";
    bool result = isMatch(s, p);
    if (result) 
        printf("true\n");
    else
        printf("false\n");
}
// @lc code=end
